package com.company.singletonExample;

import java.util.Arrays;

/**
 * Created by yijy on 2017/8/2.
 * 冒泡排序、二分法（二叉查找法）
 */
public class CalculationType {

    public static void main(String[] args) {
        int[] arr= {5,0,1,9,2,11,10,20,6,3,21,22,23,26,29,33,233,234,235,32,31,43};
        bubbleSort(arr);
        System.out.println("冒泡算法："+Arrays.toString(arr));
        int k= indexOf(3,arr);
        System.out.println(k);
        int[] arr1= {3,1,2,10,5};
        quick(arr1,0,arr1.length);
    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    public void bubbleSort2(int[] arr){
        System.out.println("----------------------这是冒泡排序算法-----------");
        long start = System.currentTimeMillis();
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j<=arr.length-1;j++){
                if(arr[i]>arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] =temp;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }

    /**
     * 二分法（二叉查找法）
     * @param value
     * @param arr
     * @return
     */
    public static int indexOf(int value,int[] arr){
        int low = 0;
        int height=arr.length-1;
        int middle;
        while (low<height){
            middle = (low+height)/2;
            if(arr[middle]==value){
                System.out.println(middle);
                return middle;
            }else if(arr[middle]>value){
                if(height==middle){
                    return -3;
                }
                height = middle;
                System.out.println("low:"+low+"  ,height:"+height);
            }else{
                if(low==middle){
                    return -2;
                }
                low = middle;
                System.out.println("low:"+low+"  ,height:"+height);
            }
        }
        return -1;
    }

    /**
     * 快排
     * @param a
     * @param low
     * @param high
     */
    public static void quick(int a[],int low,int high){
        int i=low;
        int j=high,temp;
        int key = a[low];
        while (true){
            while ((++i)<high-1 && a[i]<key );
            while ((--j)>low && a[j]>key );
            if(i>=j){
                break;
            }
            temp = a[i];
            a[i] = a[j];
            a[j]=temp;
        }
        a[low] = a[j];
        a[j] = key;
        System.out.println(Arrays.toString(a));
        if(low < j)
            quick(a,low, j);

        if(high > i)
            quick(a,i, high);
    }

}
